package com.wtgroup.demo.mianshi.算法.第k小数;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.ABTest;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;

import java.util.Arrays;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/16 21:19
 */
public class D_GetKth {

    public static void main(String[] args) {
        testP1();
    }

    /**
     * sort            3color            -
     * 2毫秒  48毫秒  -46
     * ---
     * iter: 100
     */
    private static void testP1() {
        D_Sort dSort = new D_Sort();
        D_3Color d3Color = new D_3Color();
        ABTest abTest = new ABTest("sort", "3color");

        int len = RandomUtil.randomInt(0, 1000);
        int[] nums = RandomUtil.randomArray(len, -1000, 1001);
        // int[] nums = {5, 3, 2};
        // len = nums.length;
        int[] copy1 = Arrays.copyOf(nums, len);
        int[] copy2 = Arrays.copyOf(nums, len);
        int k = RandomUtil.randomInt(Math.min(1, len), len + 1);

        for (int i = 0; i < 100; i++) {
            abTest.runA(() -> dSort.getKth(copy1, k));
            abTest.runB(() -> d3Color.getKth(copy2, k));
        }

        abTest.print();
    }

    private static void test() {
        Judger.of(() -> {
            int len = RandomUtil.randomInt(0, 1000);
            int[] nums = RandomUtil.randomArray(len, -1000, 1001);
            // int[] nums = {5, 3, 2};
            // len = nums.length;
            int[] copy1 = Arrays.copyOf(nums, len);
            int[] copy2 = Arrays.copyOf(nums, len);
            int k = RandomUtil.randomInt(Math.min(1, len), len + 1);

            int refer = new D_Sort().getKth(copy1, k);
            int res = new D_3Color().getKth(copy2, k);
            return res == refer;
        }).start().print();
    }

    static class D_Sort {
        public int getKth(int[] nums, int k) {
            if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
                return Integer.MIN_VALUE;
            }
            Arrays.sort(nums);
            return nums[k-1];
        }
    }

    static class D_3Color {
        public int getKth(int[] nums, int k) {
            if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
                return Integer.MIN_VALUE;
            }

            // getKth0 里 k 表示下标, 从 0 开始
            return getKth0(nums, k-1, 0, nums.length - 1);
        }

        int getKth0(int[] nums, int k, int L, int R) {
            if (L == R) {
                return nums[L];
            }

            int[] bounds = partition(nums, L, R);
            int left = bounds[0], right = bounds[1];
            if (k < left) {
                // k小一定在 左区
                return getKth0(nums, k, L, left - 1);
            } else if (k <= right) {
                // 中区, 就是第k小, 任意返回一个即可
                return nums[left];
            } else {
                // k小一定在 右区
                return getKth0(nums, k, right+1, R);
            }

        }

        private int[] partition(int[] nums, int L, int R) {
            if (L > R) {
                return new int[]{-1, 1};
            }

            int pivot = nums[R];
            int left = L, right = R;
            int i = L;
            while (i <= right) {
                if (nums[i] > pivot) {
                    Tools.swap(nums, i, right);
                    right--;
                } else if (nums[i] < pivot) {
                    Tools.swap(nums, i, left);
                    left++;
                    i++;
                } else {
                    i++;
                }
            }

            return new int[]{left, right};
        }
    }

}
